package SwordFingerOffer;

public class Q36_TreeToDoublyList {
    //二叉搜索树转双向链表
    //输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
    // 要求不能创建任何新的节点，只能调整树中节点指针的指向。

    static class Info{
        TreeNode min;
        TreeNode max;
        public Info(TreeNode min, TreeNode max) {
            this.min = min;
            this.max = max;
        }
    }


    public static TreeNode treeToDoublyList(TreeNode root) {
        if (root == null){
            return null;
        }
        //根据题意  首尾相连
        Info res = process(root);
        if (res.min != null){
            res.min.left = res.max;
        }
        if (res.max != null){
            res.max.right = res.min;
        }
        return res.min;
    }

    //整合出 info 类
    public  static Info process(TreeNode root) {

        if (root == null){
            return new Info(null,null);
        }

        //信息
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);

        //左指针为左子树最大
        root.left = leftInfo.max;
        //右指针为右子树最小
        root.right = rightInfo.min;

        if (leftInfo.max != null){
            leftInfo.max.right = root;
        }
        if (rightInfo.min != null){
            rightInfo.min.left = root;
        }

        return new Info(leftInfo.min == null? root : leftInfo.min,
                rightInfo.max == null? root : rightInfo.max);

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        TreeNode node = treeToDoublyList(root);
        System.out.println(node);

    }
}
